package J.算法.查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class A_SearchStudy {
    public static void main(String[] args) {

        int[] arr = new int[]{1,8,9,13,122};
       // System.out.println(BinarySearch(arr,5,0,arr.length-1));
       // List<Integer> list = BinarySearch1(arr,9,0,arr.length-1);
        System.out.println(FibonacciSearch(arr,1));
    }

    /**
     * 线性查找
     */
    public static int SeqSearch(int[] arr,int value){
         for (int i=0;i<arr.length;i++){
             if (arr[i]== value){
                 return i;
             }
         }
         return -1;
    }

    /**
     * 二分查找--元素不重复，返回单一位置
     */
    public static int BinarySearch(int[] arr,int value,int left,int right){

        if (left>right){
            return -1;
        }
        int mid = (left+right)/2;

        if (arr[mid]> value){
            return BinarySearch(arr,value,left,mid-1);//
        }else if (arr[mid]<value){
            return BinarySearch(arr,value,mid+1 ,right);
        }else {
            return mid;
        }


    }
    /**
     * 非递归的方法
     */

    public int search(int[] nums, int target) {
        int pivot, left = 0, right = nums.length - 1;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (nums[pivot] == target) return pivot;
            if (target < nums[pivot]) right = pivot - 1;
            else left = pivot + 1;
        }
        return -1;
    }


    /**
     * 二分查找--元素有重复，返回所有位置的集合
     */
    public static ArrayList<Integer> BinarySearch1(int[] arr, int value, int left, int right){

        if (left>right){
            return new ArrayList<>();
        }
        int mid = (left+right)/2;

        if (arr[mid]> value){
            return BinarySearch1(arr,value,left,mid-1);//
        }else if (arr[mid]<value){
            return BinarySearch1(arr,value,mid+1 ,right);
        }else {

            ArrayList<Integer> rs = new ArrayList<>();
            rs.add(mid);
            //向左扫描
            int temp = mid-1;
            while (true){
                if (temp <0 || arr[temp] != value){
                    break;
                }
                rs.add(temp);
                temp -=1;

            }

            //右扫描
            temp = mid+1;
            while (true){
                if (temp >arr.length-1 || arr[temp] != value){
                    break;
                }
                rs.add(temp);
                temp +=1;

            }

            //返回结果
            return rs;


        }




    }

    /**
     * 插值查找
     */
    public static int insertSearch(int[] arr,int value,int left,int right){

        if (left>right || value<arr[0] || value > arr[arr.length-1]){
            return -1;
        }

        int mid = left + (right-left)*(value-arr[left])/(arr[right]-arr[left]);
        int midValue = arr[mid];

        if (midValue > value){
            return insertSearch(arr,value,left,mid-1);
        }else if (midValue< value){
            return insertSearch(arr,value,mid+1,right);
        }else {
            return mid;
        }

    }

    /**
     * 斐波那契查找--采用非递归方法
     * @param arr
     * @param value
     * @param left
     * @param right
     * @return
     */
    public  static  int MaxSize=20;//fib数列的长度
    public static int FibonacciSearch(int[] arr,int value){
        int low =0;
        int high =arr.length-1;
        int k =0;//分割数值下标
        int mid = 0;

        //首先需要先构建一个fib数列
        int[] fib = getFib();
        // 确定mid计算公式中的k
        while (arr.length>fib[k]-1){
            k++;
        }

        int[] temp = Arrays.copyOf(arr,fib[k]);//数组进行扩展 扩展后的长度为fib【k】
        //扩展的部分填充high位置的数值
        for (int i=high+1;i< temp.length;i++){
            temp[i] = temp[high];
        }

        //非递归 采用循环
        while (low<=high){
            mid = low+ fib[k-1]-1;
            if (value<temp[mid]){
                high = mid-1;
                k--;
            }else if (value>temp[mid]){
                low = mid+1;
                k-=2;
            }else {//找到

                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }

            }

        }
        return -1;

    }

    //获取fib数列的函数
    public static int[] getFib(){
        int[] fib = new int[MaxSize];
        fib[0] = 1;
        fib[1] = 1;

        for (int i=2;i<MaxSize;i++){
            fib[i] = fib[i-1]+fib[i-2];
        }

        return fib;

    }


}
